Various methods have been used for compressing image data, and one of the methods is called “BTC” (Block Truncation Coding).
According to this method, image data (hereinafter, sometimes referred to simply as “image”) is divided into a plurality of blocks, and pixels in individual blocks are expressed by approximated colors to reduce the number of colors in the individual blocks and to thereby reduce an amount of data.
For example, the following shows the specific process. First, an average value of density values of pixels in each divided block is obtained. Then, each of the pixels is classified into a group of pixels having density values higher than the average value and a group of pixels having density values lower than the average value. Further, for each of the groups, an average value of the density values for each of the color components such as R (Red), G (Green), and B (Blue) is obtained. Thereafter, a color expressed by the individual average values is determined as an approximated color (representative color) for each individual group. With this arrangement, an identical representative color is assigned to all the pixels in the same group. This process is repeated for all blocks included in the image data. As an art related to this kind of method, there is proposed a method disclosed in JP2001-338284A as described below.
According to the method disclosed in JP2001-338284A, variance of each color (color component) is calculated for each small area (block) included in image data, and a color (color component) of which the variance is the largest is determined as a target color. An average value is obtained for this target color in each small area. Then, the pixels in each small area are divided into groups based on the average value. In other words, the pixels are divided into a group of pixels having a density higher than the average value and a group of pixels having a density lower than the average value. Next, an average value of density values for each color component of pixels in each of the groups is obtained. A color expressed as a result of this is determined as a representative color of each of the groups. Then, it is determined whether a quantity of representative colors thus decided is greater than a desired quantity of colors. If it is less than the desired quantity of colors, then further grouping is performed. If it is equal to or larger than the desired quantity of colors, then another small area will be processed.
As described above, according to the BTC, an image in a block is converted into an image having a smaller number of colors. As a result, by allowing a certain amount of degradation in image quality, the amount of data is reduced.
Hereinafter, a description will be given of a compression ratio according to the BTC with reference to FIG. 16. FIG. 16(a) illustrates a block BK having a size of 8 by 8 matrix of pixels. The block BK includes images represented by a line drawing portion JS and a background portion thereof. In this example, the line drawing portion JS and the background portion are expressed in blue (shown by hatching) and gradation in red fading gradually from a right-bottom portion toward a left-top portion.
In FIG. 16(a), if the image in the block BK is expressed by 24 bits of RGB color (8 bits for each color component), the amount of data of this image becomes 1536 bits resulting from 24 bits×64 pixels.
For example, when the image in this block is converted, by using the BTC, into an image illustrated in FIG. 16(c) expressed in four approximated colors which are depicted in FIG. 16(b), the amount of data will be as follows. Here, the four colors that are shown individually by two-bit numerals “00”, “01”, “10”, and “11” are blue, light red, deeper red, and much deeper red, respectively.
The four approximated colors require the amount of data of 96 bits resulting from 24 bits×4 colors. Since there are four approximated colors, 2 bits are required to identify individual colors. Since there are 64 pixels (8 by 8) in the block BK, 128 bits resulting from 2 bits×64 pixels are required to associate representative colors to individual pixels in the block BK. As a result, the converted image can be expressed by 224 bits which is a result of 96 bits+128 bits. In this example, the amount of data before conversion, i.e., 1536 bits, is compressed into the amount of data after conversion, i.e., 224 bits, achieving a compression ratio of about 14.6%.
This compression ratio becomes larger as the quantity of the approximated colors are reduced or the size of the block is made larger. FIG. 17 illustrates a relationship between the size of the block and the compression ratio. It is important to properly select the representative colors from the block for performing effective compression.